﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/*
 * 
Say you factor 100: 1,2,4,5,10,20,25,50,100. The sum is 217. The prime factorization is 2*2*5*5. This function gives you [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

Factoring 8: 1,2,4,8. The sum is 15. The prime factorization is 2*2*2. This function gives you [2*(2*(2+1)+1)+1]=15

The algorithm boils down to (using Fi to mean the ith index of the factor F or F sub i):
 * 
 * http://www.spoj.pl/problems/CZ_PROB2/
 */
namespace CSharpAlgorithm
{
    class SumofFactors2
    {
        List<int> primes = Primes.getPrimes(100);
        public SumofFactors2()
        {
            
            int t = Int32.Parse(TestConsole.ReadLine());
            while (t-- > 0)
            {
                int num = Int32.Parse(TestConsole.ReadLine());
                Dictionary<int, int> factors = factorization(num);
                long result = 1;
                foreach (KeyValuePair<int, int> factor in factors)
                {
                    long p = 1;
                    long sum = 1;
                    for (int i = 1; i <= factor.Value; i++)
                    {
                        p *= factor.Key;
                        sum += p;
                    }
                    result *= sum;
                }
                Console.WriteLine(result);
            }
        }

        public Dictionary<int, int> factorization(int number)
        {
            Dictionary<int, int> factors = new Dictionary<int, int>();
            int value = number;
            while (!primes.Contains(value) && value != 1)
            {
                int r = (int)Math.Sqrt(value);
                bool findFactor = false;
                for (int i = 0; i < primes.Count && primes[i] <= r; i++)
                {
                    if (value % primes[i] == 0)
                    {
                        findFactor = true;
                        value /= primes[i];
                        if (factors.ContainsKey(primes[i]))
                        {
                            factors[primes[i]]++;
                        }
                        else
                        {
                            factors.Add(primes[i], 1);
                        }
                        break;
                    }
                }
                if (!findFactor)
                {
                    break;
                }
            }
            if (value != 1)
            {
                if (factors.ContainsKey(value))
                {
                    factors[value]++;
                }
                else
                {
                    factors.Add(value, 1);
                }
            }
            return factors;

        }
    }
}
